[PFDS写経]GADTs拡張で型コンストラクタに制約をつける

はじめに

７月から期が変わったこともあり、PFDS をHaskellで写経しながら読み進めています。HaskellはすごいH本を斜め読みした程度しか触っていないので写経と言ってもHaskellについて調べながら進めています。

今回はPFDS から「2.2 二分探索木」を読みました。

二分探索木

文中で取り上げられている二分探索木は以下のようなものです。

datatype Tree = E | T of Tree * Elem * Tree

Haskellで素直に書くと以下のようになると思います。

data Tree = E | T Tree a Tree

型パラメータに制約をつけたい

ところで二分探索木の性質を考えた時、上記の型パラメータaは全順序づけされている必要があります。この制約をTreeの定義に含めるにはGADTs(Generalized algebraic datatypes)拡張を使います。これによって通常の関数定義と同様に型コンストラクタTのパラメータaにOrdクラスのインスタンスであるという制約をつけることができます。

{-# LANGUAGE GADTs #-}

data Tree where 
  E :: Tree
  T :: (Ord a) => Tree -> a -> Tree -> Tree

まとめ

GADTs拡張によって二分木の要素を全順序付けられている制約をつけることができました。PFDSの方の進捗は思ったように進みませんが、Haskellの勉強にはなっているので引き続きやっていきます。

参考

• Data declaration with constraint
• Haskell/GADT